package bin_tree.leetcode;

/**
 * 根据前序和中序遍历结果，还原二叉树
 * @author yuisama
 * @date 2021/12/08 19:06
 **/
public class Num105 {
    // 当前处理到前序遍历的哪个位置
    int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeInternal(preorder,inorder,0,inorder.length);
    }

    /**
     * 根据传入的前序遍历和中序遍历的部分区间
     * [left,right) 表示当前节点中序遍历结果
     * 左区间连接到根节点左侧
     * 右区间连接到根节点右侧
     * @param preOrder 前序遍历结果
     * @param inOrder 中序遍历结果
     * @param left
     * @param right
     * @return
     */
    public TreeNode buildTreeInternal(int[] preOrder,int[] inOrder,int left,int right) {
        if(left >= right) {
            return null;
        }
        if (index >= preOrder.length) {
            return null;
        }
        TreeNode root = new TreeNode(preOrder[index]);
        index ++;
        int pos = find(inOrder,left,right,root.val);
        root.left = buildTreeInternal(preOrder,inOrder,left,pos);
        root.right = buildTreeInternal(preOrder,inOrder,pos + 1,right);
        return root;
    }
    /**
     * 在当前中序遍历中寻找root.val对应的索引值
     * @param inOrder
     * @param left
     * @param right
     * @param val
     * @return
     */
    private int find(int[] inOrder, int left, int right, int val) {
        for (int i = left; i < right; i++) {
            if (inOrder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}